package pers.sloera.leetcode.existWord;

/**
 * 79. 单词搜索
 * <p>
 * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 * <p>
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 * <p>
 * <p>
 * <p>
 * 示例:
 * <p>
 * board =
 * [
 * ['A','B','C','E'],
 * ['S','F','C','S'],
 * ['A','D','E','E']
 * ]
 * <p>
 * 给定 word = "ABCCED", 返回 true
 * 给定 word = "SEE", 返回 true
 * 给定 word = "ABCB", 返回 false
 * <p>
 * <p>
 * 提示：
 * <p>
 * board 和 word 中只包含大写和小写英文字母。
 * 1 <= board.length <= 200
 * 1 <= board[i].length <= 200
 * 1 <= word.length <= 10^3
 *
 * @author SloeraN
 * @version 1.0
 * @class pers.sloera.leetcode.existWord.Solution
 * @date 2020/9/13
 */
public class Solution {

    public boolean exist(char[][] board, String word) {
        for (int x = 0; x < board.length; x++) {
            for (int y = 0; y < board[x].length; y++) {
                // 以网格中的每一个元素做为起始查找单词
                boolean[][] repeat = new boolean[board.length][board[0].length];
                if (isExist(word, x, y, board, repeat)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 查找网格中，(x,y)位置元素开头的word
     *
     * @param word 待查找单词
     * @param x 当前x坐标
     * @param y 当前y坐标
     * @param board 网格
     * @param repeat 已遍历记数
     * @return boolean
     * @date 2020/9/13
     */
    private boolean isExist(String word, int x, int y, char[][] board, boolean[][] repeat) {
        // byte[][] repeat = new byte[repeat.length][repeat[0].length];
        // for (int i = 0; i < clone.length; i++) {
        //     clone[i] = repeat[i].clone();
        // }
        // TODO 浅拷贝同深拷贝
        // System.arraycopy(repeat, 0, clone, 0, repeat.length);
        boolean currentFlag = board[x][y] == word.charAt(0);
        // 如果当前元素不匹配，无需进行后续步骤
        if (!currentFlag) {
            return false;
        }
        // 剔除重复元素
        if (repeat[x][y]) {
            return false;
        } else {
            repeat[x][y] = true;
        }
        if (word.length() <= 1) {
            return currentFlag;
        }
        String substring = word.substring(1);
        int nextX;
        int nextY;
        if (x > 0) {
            nextX = x - 1;
            nextY = y;
            if (isExist(substring, nextX, nextY, board, repeat)) {
                return true;
            }
        }
        if (x < board.length - 1) {
            nextX = x + 1;
            nextY = y;
            if (isExist(substring, nextX, nextY, board, repeat)) {
                return true;
            }
        }
        if (y > 0) {
            nextX = x;
            nextY = y - 1;
            if (isExist(substring, nextX, nextY, board, repeat)) {
                return true;
            }
        }
        if (y < board[x].length - 1) {
            nextX = x;
            nextY = y + 1;
            if (isExist(substring, nextX, nextY, board, repeat)) {
                return true;
            }
        }
        repeat[x][y] = false;
        return false;
    }
}
